//
//  AStarFinder.m
//  TestAStart
//
//  Created by Sun Rujia on 11-11-17.
//  Copyright 2011 CDC Games. All rights reserved.
//

#import "AStarFinder.h"
#import "MSGameManager.h"

@implementation AStarFinder {
    NSArray *_tileCoordArray;
}

@synthesize openTable;
@synthesize closeTable;
@synthesize runTable;

- (id)initWithTileCount:(NSInteger)tileCount{

	if ((self = [super init])) {
		
		openTable = [[NSMutableArray alloc] initWithCapacity:tileCount];
		closeTable = [[NSMutableArray alloc] initWithCapacity:tileCount];
        runTable = [[NSMutableArray alloc] initWithCapacity:tileCount];
	}
	return self;
}

- (void)clearData {
    [openTable removeAllObjects];
    [closeTable removeAllObjects];
    [runTable removeAllObjects];
}

- (BOOL)start:(TilePoint *)startPoint_ EndPoint:(TilePoint *)endPoint_{
    [self clearData];
	[openTable addObject:startPoint_];
	
	startPoint = startPoint_;
	endPoint = endPoint_;
	
	TilePoint *curr=nil;
	while ([openTable count] > 0){
		curr = [self bestTilePoint:curr];
		if (curr != nil) {
			
			[closeTable addObject:curr];
            [runTable addObject:curr];
	
			if ([self nextTile:curr X:curr.x Y:curr.y-1] == YES) {
				break;
			}
		
			if ([self nextTile:curr X:curr.x+1 Y:curr.y] == YES) {
				break;
			}
			
			if ([self nextTile:curr X:curr.x Y:curr.y+1] == YES) {
				break;
			}
			
			if ([self nextTile:curr X:curr.x-1 Y:curr.y] == YES) {
				break;
			}
        } else {
            [runTable removeAllObjects];;
        }
	}
    
//	NSLog(@"closeTable num:%d\n",[closeTable count]);
    if (runTable.count > 0) {
        TilePoint *lastPoint = [runTable lastObject];
        if([self isComparePoint:lastPoint And:endPoint]) {
            return YES;
        }
    }
    return NO;
}

- (TilePoint *)bestTilePoint:(TilePoint *)p{
	
	TilePoint *best = nil;
	
	if ([openTable count] == 0) {
		return nil;
	}else {
		for (NSInteger i = 0; i < [openTable count]; i++) {
			if (best == nil) {
				best = [openTable objectAtIndex:i];
                if (best != nil && p!=nil && [self isComparePoint:best.parent And:p] == NO) {
					best = nil;
				}
			} else {
				TilePoint *best2 = [openTable objectAtIndex:i];
				if (p!=nil && [self isComparePoint:best2.parent And:p] == YES) {
					best = best.f >= best2.f ? best2 : best;
				}
			}		
		}
		[openTable removeObject:best];
		return best;
	}
}

- (BOOL)isComparePoint:(TilePoint *)p1 And:(TilePoint *)p2{

	if (p1.x == p2.x && p1.y == p2.y) {
		return YES;
	}else {
		return NO;
	}

}

- (BOOL)isInOpenTable:(TilePoint *)p{

	for (TilePoint *pTemp in openTable){
	
		if ([self isComparePoint:pTemp And:p] == YES) {
			return YES;
		}
	}
	return NO;
}

- (BOOL)isInCloseTable:(TilePoint *)p{
	
	for (TilePoint *pTemp in closeTable){
		
		if ([self isComparePoint:pTemp And:p] == YES) {
			return YES;
		}
	}
	return NO;
}

- (NSInteger)calculateHPower:(TilePoint *)p{
	return abs(endPoint.x - p.x) + abs(endPoint.y - p.y);
}

- (NSInteger)calculateGPower:(TilePoint *)p{
	return abs(startPoint.x - p.x) + abs(startPoint.y - p.y);
}

- (TilePoint *)getFromOpenPath:(TilePoint *)p{

	for (TilePoint *pp in openTable){
		if ([self isComparePoint:pp And:p] == YES) {
			return pp;
		}
	}
	return nil;
}

- (BOOL)nextTile:(TilePoint *)curr X:(NSInteger)x Y:(NSInteger)y{

	TilePoint *next = [[TilePoint alloc] initWitTilePoint:x Y:y];
	next.parent = curr;
	
	if ([self isComparePoint:next And:endPoint]) {
		[closeTable addObject:next];
        [runTable addObject:next];
//		NSLog(@"find end point !!!!!!!\n");
		return YES;
	}
	
	if ([self isInCloseTable:next] == NO && [self isEnableTile:next.x Y:next.y] == YES) {
		if ([self isInOpenTable:next] == NO) {
			
			next.g = 14 + next.parent.g;
			next.f = next.g + [self calculateHPower:next];
			
			[openTable addObject:next];
		}else {
			TilePoint *next2 = [self getFromOpenPath:next];
			if (next2.f > next.f) {
				next2.parent = curr;
				next2.g = 14 + next2.parent.g;
				next2.f = next2.g + [self calculateHPower:next2];
			}
		}		
	}
	return NO;
}

- (BOOL)isEnableTile:(NSInteger)x Y:(NSInteger)y{
//	CCTMXTiledMap *map = [CCTMXTiledMap tiledMapWithTMXFile:@"tile_map.tmx"];
//	CCTMXLayer *layer = [map layerNamed:@"layer0"];	
//	
//	if (x < 0 || y < 0 || x > 22 || y > 15) {
//		
//		return NO;
//	}else {
//			
//		//int gid = [layer tileGIDAt:ccp(x,y)];
////		if (gid == 2) {
////			return NO;
////		}else {
//			return YES;
//		//}
//		
//	}
    for (NSValue *value in _tileCoordArray) {
        if (value.CGPointValue.x == x && value.CGPointValue.y == y) {
            return YES;
        }
    }
    return NO;
}

- (void)setEnableTile:(NSArray *)tileCoordArray {
    _tileCoordArray = tileCoordArray;
}

@end

@implementation TilePoint

@synthesize x;
@synthesize y;
@synthesize f;
@synthesize g;
@synthesize h;
@synthesize parent;

- (id)initWitTilePoint:(NSInteger)x_ Y:(NSInteger)y_ {
    self = [super init];
	if (self) {
		x = x_;
		y = y_;
	}
	return self;
}

@end